



<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <title>2. 01背包问题 - AcWing题库</title>
    

<meta charset="UTF-8">
<meta name="keywords" content="背包九讲 , 模板题，01背包问题，AcWing题库"/>
<meta name="description" content="高质量的算法题库"/>
<meta name="baidu-site-verification" content="UW1SBiMHO7" />
<meta name="google-site-verification" content="YTgbOq_0TDShJS6KTcUYCQoAAZTm308SJ7ibsafBD_Y" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<link rel="shortcut icon" type="image/png" href="https://cdn.acwing.com/static/web/img/favicon.ico"/>
<link rel="stylesheet" href="https://cdn.acwing.com/static/bootstrap-3.3.7-dist/css/bootstrap.min.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/web/node_modules/bootstrap-toggle/css/bootstrap-toggle.min.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/signform.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/jquery-ui-dist/jquery-ui.min.css">

    <link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/success_modal.css" />


    
        <link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/wss/chat/chat_list-0.0.1.css">
    

<!--link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/pace.css"-->
<!--script src="https://cdn.acwing.com/static/web/js/pace.js"></script-->
<script>
    let onbeforeunload_functions = [];
</script>


<style>
    /* latin */
    @font-face {
      font-family: 'Satisfy';
      font-style: normal;
      font-weight: 400;
      src: local('Satisfy Regular'), local('Satisfy-Regular'), url(https://cdn.acwing.com/static/web/fonts/rP2Hp2yn6lkG50LoCZOIHQ.woff2) format('woff2');
      unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
    }

    /* latin-ext */
    @font-face {
      font-family: 'Lato';
      font-style: italic;
      font-weight: 400;
      src: local('Lato Italic'), local('Lato-Italic'), url(https://cdn.acwing.com/static/web/fonts/S6u8w4BMUTPHjxsAUi-qJCY.woff2) format('woff2');
      unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
    }
    /* latin */
    @font-face {
      font-family: 'Lato';
      font-style: italic;
      font-weight: 400;
      src: local('Lato Italic'), local('Lato-Italic'), url(https://cdn.acwing.com/static/web/fonts/S6u8w4BMUTPHjxsAXC-q.woff2) format('woff2');
      unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
    }
    /* latin-ext */
    @font-face {
      font-family: 'Lato';
      font-style: italic;
      font-weight: 700;
      src: local('Lato Bold Italic'), local('Lato-BoldItalic'), url(https://cdn.acwing.com/static/web/fonts/S6u_w4BMUTPHjxsI5wq_FQft1dw.woff2) format('woff2');
      unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
    }
    /* latin */
    @font-face {
      font-family: 'Lato';
      font-style: italic;
      font-weight: 700;
      src: local('Lato Bold Italic'), local('Lato-BoldItalic'), url(https://cdn.acwing.com/static/web/fonts/S6u_w4BMUTPHjxsI5wq_Gwft.woff2) format('woff2');
      unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
    }
    /* latin-ext */
    @font-face {
      font-family: 'Lato';
      font-style: normal;
      font-weight: 400;
      src: local('Lato Regular'), local('Lato-Regular'), url(https://cdn.acwing.com/static/web/fonts/S6uyw4BMUTPHjxAwXjeu.woff2) format('woff2');
      unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
    }
    /* latin */
    @font-face {
      font-family: 'Lato';
      font-style: normal;
      font-weight: 400;
      src: local('Lato Regular'), local('Lato-Regular'), url(https://cdn.acwing.com/static/web/fonts/S6uyw4BMUTPHjx4wXg.woff2) format('woff2');
      unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
    }
    /* latin-ext */
    @font-face {
      font-family: 'Lato';
      font-style: normal;
      font-weight: 700;
      src: local('Lato Bold'), local('Lato-Bold'), url(https://cdn.acwing.com/static/web/fonts/S6u9w4BMUTPHh6UVSwaPGR_p.woff2) format('woff2');
      unicode-range: U+0100-024F, U+0259, U+1E00-1EFF, U+2020, U+20A0-20AB, U+20AD-20CF, U+2113, U+2C60-2C7F, U+A720-A7FF;
    }
    /* latin */
    @font-face {
      font-family: 'Lato';
      font-style: normal;
      font-weight: 700;
      src: local('Lato Bold'), local('Lato-Bold'), url(https://cdn.acwing.com/static/web/fonts/S6u9w4BMUTPHh6UVSwiPGQ.woff2) format('woff2');
      unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
    }
</style>
<script src="https://cdn.acwing.com/static/jquery/js/jquery-3.3.1.min.js"></script>
<script src="https://cdn.acwing.com/static/bootstrap-3.3.7-dist/js/bootstrap.min.js"></script>
<script src="https://cdn.acwing.com/static/web/node_modules/bootstrap-toggle/js/bootstrap-toggle.min.js"></script>
<script src="https://cdn.acwing.com/static/jquery-ui-dist/jquery-ui.min.js"></script>
<script src="https://cdn.acwing.com/static/web/node_modules/jquery.cookie/jquery.cookie.js"></script>
<script>
    $(document).ready(function () {
        var csrftoken = $.cookie('csrftoken');

        function csrfSafeMethod(method) {
            // these HTTP methods do not require CSRF protection
            return (/^(GET|HEAD|OPTIONS|TRACE)$/.test(method));
        }

        $.ajaxSetup({
            beforeSend: function(xhr, settings) {
                if (!csrfSafeMethod(settings.type) && !this.crossDomain) {
                    xhr.setRequestHeader("X-CSRFToken", csrftoken);
                }
            },
            cache: true
        });
    });
</script>
<script src="https://cdn.acwing.com/static/web/js/signform-0.0.1.js"></script>
<script src="https://cdn.acwing.com/static/web/js/handlebars-v1.3.0.js"></script>
<script src="https://cdn.acwing.com/static/web/js/effect_anchor.js"></script>

    <script>
    let chat_state = {
        me_id: 96997,
    };
</script>
<div style="display: none;">
    <div id="message_template_me">
        <div class="row" style="margin: 0; margin-bottom: 10px;">
            <div class="col-xs-2 pull-right" style="width: 30px; padding: 0; margin-right: 10px;">
                <a href="https://message_host_space_url">
                    <img class="img-responsive img-circle" width="30px" height="30px" src="https://www.acwing.com/static/web/img/favicon.ico" alt="我的头像">
                </a>
            </div>
            <div class="col-xs-10 pull-right">
                <span class="chat-bubble-me pull-right" style="word-break: break-all;">
                    message_content
                </span>
            </div>
        </div>
    </div>
    <div id="message_template_you">
        <div class="row" style="margin: 0; margin-bottom: 10px;">
            <div class="col-xs-2" style="width: 30px; padding: 0; margin-left: 10px;">
                <a href="https://message_host_space_url">
                    <img class="img-responsive img-circle" width="30px" height="30px" src="https://www.acwing.com/static/web/img/favicon.ico" alt="好友头像">
                </a>
            </div>
            <div class="col-xs-10">
                <span class="chat-bubble-you pull-left" style="word-break: break-all;">
                    message_content
                </span>
            </div>
        </div>
    </div>
    <div id="message_create_time">
        <div class="text-center">
            <span class="chat-time-format">message create time</span>
        </div>
        <br>
    </div>
    <div id="message_code_template">
        <a id="message_code_template_0_message_id_0" style="cursor:pointer;">
            <img src="https://cdn.acwing.com/static/web/img/chat/code.png" width="75px" style="margin: -17px -22px -14px -22px;" alt="代码">
        </a>
    </div>
    <div id="message_emoji_gif_template">
        <a style="cursor:pointer;">
            <img src="https://www.acwing.com/static/web/img/favicon.ico"
                 width="100px"
                 style="margin: 0"
                 title="emoji_gif_description"
                 alt="表情动画">
        </a>
    </div>
</div>
    <script src="https://cdn.acwing.com/static/web/js/wss/chat/utils.js"></script>



    <script src="https://cdn.acwing.com/static/web/third_party/ace-builds/src-min-noconflict/ace.js" type="text/javascript" charset="utf-8"></script>
    <script src="https://cdn.acwing.com/static/web/third_party/ace-builds/src-min-noconflict/ext-language_tools-0.0.1.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/editor/code_completer/dist/code_completer-0.0.8.min.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/editor/utils-0.0.1.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/wss/chat/emoji-data.js"></script>




<script>
    let user_state = {
        is_authenticated: true,
        is_mobile: false,
    };
    if (user_state.is_authenticated){
        user_state.user_id = 96997;
    }
    
</script>
<script>
    let GLOBAL_COMMENT_SONS = {};
</script>
<style>
    
        #acwing_body {
            background: white url("https://cdn.acwing.com/static/web/img/background.png") fixed;
            background-size: auto;
        }
    

    
    @media (min-width: 768px) and (max-width: 1000px) {
       .collapse {
           display: none !important;
       }
    }
</style>


<link rel="stylesheet" href="https://cdn.acwing.com/static/plugins/css/ace.min.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/martor/css/martor.min.css">

    <link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/martor.css">

<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/file_system/file/content/comment.css">


    <link rel ="stylesheet" href="https://cdn.acwing.com/static/web/css/style-0.0.8.css">

<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/base/navbar.css">

    

<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/file_system/gui/window/base-0.0.4.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/file_system/file/content/whole/application/file_explorer/base-0.0.1.css">
<link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/file_system/gui/taskbar/base-0.0.4.css">
<script>
    let DESKTOP_STATE_WINDOW_OPERATE_OPEN_URL = "/file_system/gui/window/operate/open/666/";
    let DESKTOP_STATE_TASKBAR_SEARCH_URL = "/file_system/gui/search/base/search/";
</script>
<script src="https://cdn.acwing.com/static/web/js/file_system/file/content/whole/application/file_explorer/dist/file_explorer-0.0.5.min.js"></script>
<script src="https://cdn.acwing.com/static/web/js/file_system/gui/dist/gui-0.0.15.min.js"></script>
<script>
    $(document).ready(function () {
        let urls = {
            add: "/file_system/file/operation/content/add/",
            update: "/file_system/file/operation/content/update/",
            delete: "/file_system/file/operation/content/delete/",
            update_refactor_rename: "/file_system/file/operation/content/update/refactor/rename/",
            command_ls: "/file_system/file/operation/content/command/ls/",
            command_cp: "/file_system/file/operation/content/command/cp/",
            command_mv: "/file_system/file/operation/content/command/mv/",
            command_read: "/file_system/file/operation/content/command/read/",
        };
        desktop_state.os.builtin.api.file.operation.set(urls);

        let applications = {
            file_explorer: 284475,
            ac_editor: 172575,
            ac_saber: 118289,
            settings: 589618,
            ac_chat: 994425,
        };
        desktop_state.os.builtin.application.set(applications);

        let configs = {
            media_url: "https://cdn.acwing.com/media/",
        };
        desktop_state.os.builtin.settings.set(configs);

        let auto_open_apps = [];
        
            auto_open_apps.push({
                title: "AC Chat",
                icon: "https://cdn.acwing.com/media//file_system/file/application/icon/2220490481555590627-128_UQONKkk.png",
                file_id: 994425,
            });
        
        desktop_state.taskbar.widgets.apps.set(auto_open_apps);
    });
</script>

    
    
        <link rel="stylesheet" href="https://cdn.acwing.com/static/web/css/problem/content-0.0.2.css">
    
    

</head>
<body id="acwing_body" style="min-height: 100vh;">

 
    

<div class="panel panel-default fs-gui-taskbar"
        
            style="width: 100vw;"
        >
    <div class="panel-body fs-gui-taskbar-body dropup">
        <div class="panel panel-default fs-gui-taskbar-begin-menu">
    <div class="panel-body" style="padding: 0;">
        <div class="fs-gui-taskbar-begin-menu-item fs-gui-taskbar-begin-menu-item-file">
            文件
        </div>
        <div class="fs-gui-taskbar-begin-menu-item fs-gui-taskbar-begin-menu-item-application">
            应用
        </div>
        <hr style="height: 1vh; margin: 1vh;">
        <div class="fs-gui-taskbar-begin-menu-item fs-gui-taskbar-begin-menu-item-settings">
            设置
        </div>
    </div>
</div>
        <button class="fs-gui-taskbar-begin pull-left btn btn-default">
            <img src="https://cdn.acwing.com/static/web/img/favicon.ico" alt="开始" title="开始" style="width: 60%;" />
        </button>
        <div class="fs-gui-taskbar-search pull-left">
            <span class="glyphicon glyphicon-search fs-gui-taskbar-search-icon"></span>
            <label for="fs-gui-taskbar-search-field" class="sr-only"></label>
            <input id="fs-gui-taskbar-search-field" placeholder="在这里输入你要搜索的内容" />
        </div>
        <div class="fs-gui-taskbar-right">
            <div class="fs-gui-taskbar-task-list"></div>
            <div class="fs-gui-taskbar-widgets">
                <div class="fs-gui-taskbar-widgets-clock">
                    <div class="fs-gui-taskbar-widgets-clock-time">16:10</div>
                    <div class="fs-gui-taskbar-widgets-clock-date">2021-05-30</div>
                </div>
                <div class="fs-gui-taskbar-widgets-apps">
                    
                        <div class="fs-gui-taskbar-widgets-apps-item fs-gui-taskbar-widgets-apps-item-994425" title="AC Chat">
                            <img src="https://cdn.acwing.com/media/file_system/file/application/icon/2220490481555590627-128_UQONKkk.png" alt="AC Chat">
                        </div>
                    
                </div>
            </div>
        </div>
    </div>
</div>


<div id="acwing_page" >
    <nav class="navbar navbar-inverse navbar-fixed-top navbar-expand-lg" style="z-index: 10;">
        <div class="container">
            <!-- Header -->
            <div class="navbar-header">
                <button type="button" class="navbar-toggle" data-toggle="collapse" data-target="#topNavBar">
                    <span class="icon-bar"></span>
                    <span class="icon-bar"></span>
                    <span class="icon-bar"></span>
                    
                </button>
                
                <a class="navbar-brand" href="/">AcWing</a>
            </div>

            <!-- Items -->
            <div class="collapse navbar-collapse" id="topNavBar">
                <ul class="nav navbar-nav">
                    <li class=""><a href="/about/">首页</a></li>
                    <li class="active"><a href="/problem/">题库</a></li>
                    <li class=""><a href="/solution/">题解</a></li>
                    <li class=""><a href="/blog/">分享</a></li>
                    <li class=""><a href="/community/">问答</a></li>
                    <li id="navigation_activity_active_id" class=""><a href="/activity/">活动</a></li>
                    <li id="navigation_competition_active_id" class=""><a href="/activity/1/competition/">竞赛</a></li>
                    <li class=""><a href="/file_system/file/content/whole/index/content/whole/application/1/">应用</a></li>
                    <li class=""><a href="/http_wss/danmu/world/">吐槽</a></li>
                </ul>

                <ul class="nav navbar-nav navbar-right">
                    
                        <li>
                            <a href="/user/myspace/notification/1/">
                                <span class="glyphicon glyphicon-bell" style="font-size: 20px;"></span>
                                
                            </a>
                        </li>
                        <li>
                            <a href="#" class="dropdown-toggle" data-toggle="dropdown">
                                <img class="img-circle" src="https://cdn.acwing.com/media/user/profile/photo/96997_sm_55fbe780ba.jpg" alt="chair_5 的头像" style="margin: -5px;" width="35px">
                                &nbsp;
                                <strong id="id_user_username">chair_5</strong>
                                <b class="caret"></b>
                            </a>
                            <ul class="dropdown-menu">
                                <li>
                                    <span style="cursor: pointer;" title="AC币">
                                        <img src="https://cdn.acwing.com/static/web/img/acb2.png"
                                             width="15px" alt="AC币图标"
                                             style="margin-left: 20px; margin-bottom: 4px;">
                                        &nbsp;
                                        <span class="hidden-sm hidden-md hidden-lg" style="color: white;">0</span>
                                        <span class="hidden-xs">0</span>
                                    </span>
                                </li>
                                <li class="divider"></li>
                                <li><a href = "/user/myspace/index/96997/">我的空间</a></li>
                                <li><a href = "/user/profile/index/">个人信息</a></li>
                                <li><a href = "/user/account/changepassword/">修改密码</a></li>
                                <li class = "divider"></li>
                                <li>
                                    <form id="signout-form" action="/user/account/signout/" method="post">
                                        <input type="hidden" name="csrfmiddlewaretoken" value="s4bKp3icqZRTpmGeEdi0rMxmm5PQ8U6yhXDwUwABkKba2tfjBHuAVuZFmEsGRkEu">
                                    </form>
                                    <a id="signout-link" style="cursor: pointer">登出</a>
                                    <script>
                                        $(document).ready(function (){
                                            $('#signout-link').click(function (){
                                                $('#signout-form').submit();
                                            });
                                        });
                                    </script>
                                </li>
                            </ul>
                        </li>
                    
                </ul>
            </div>
        </div>
    </nav>
    <div class="base_body">
    <div class="container">
    <div class="panel panel-default">
        <div class="panel-body">
            <div class="nice_font problem-content-title">
                2. 01背包问题
            </div>
            <ul class="nav nav-tabs">
                <li role="presentation" class="active">
                    <a class="problem-content-sub-btn" href="/problem/content/description/2/" style="padding-left: 30px; padding-right: 30px;">
                        <span class="glyphicon glyphicon-list-alt" style="top: 4px;"></span>
                        &nbsp;
                        题目
                    </a>
                </li>
                
                    <li role="presentation" class="">
                        <a class="problem-content-sub-btn" href="/problem/content/submission/2/" style="padding-left: 30px; padding-right: 30px;">
                            <span class="glyphicon glyphicon-list" style="top: 4px;"></span>
                            &nbsp;
                            提交记录
                        </a>
                    </li>
                
                <li role="presentation" class="">
                    <a class="problem-content-sub-btn" href="/problem/content/discussion/index/2/1/" style="padding-left: 30px; padding-right: 30px;">
                        <span class="glyphicon glyphicon-comment" style="top: 4px;"></span>
                        &nbsp;
                        讨论
                    </a>
                </li>
                
                    <li role="presentation" class="">
                        <a class="problem-content-sub-btn" href="/problem/content/solution/2/1/" style="padding-left: 30px; padding-right: 30px;">
                            <span class="glyphicon glyphicon-book" style="top: 4px;"></span>
                            &nbsp;
                            题解
                        </a>
                    </li>
                    <li role="presentation" class="">
                        <a class="problem-content-sub-btn" href="/problem/content/video/2/" style="padding-left: 30px; padding-right: 30px;">
                            <span class="glyphicon glyphicon-book" style="top: 4px;"></span>
                            &nbsp;
                            视频讲解
                        </a>
                    </li>
                
            </ul>
            <br>
            
    <div class="row">
        <div class="col-sm-9 col-xs-12">
            <div class="main-martor main-martor-content" data-field-name="content">
                <div class="section-martor">
                    <div class="ui bottom attached tab active martor-preview" data-tab="preview-tab-content">
                        <p>有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。</p>
<p>第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。</p>
<p>求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。<br />
输出最大价值。</p>
<h4>输入格式</h4>
<p>第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。</p>
<p>接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。</p>
<h4>输出格式</h4>
<p>输出一个整数，表示最大价值。</p>
<h4>数据范围</h4>
<p>$0 \lt N, V \le 1000$<br />
$0\lt v_i, w_i \le 1000$</p>
<h4>输入样例</h4>
<pre><code>4 5
1 2
2 4
3 4
4 5
</code></pre>

<h4>输出样例：</h4>
<pre><code>8
</code></pre>
                    </div>
                </div>
            </div>
        </div>
        <div class="col-sm-3 hidden-xs" style="padding-left: 0;top: -20px;">
            <div class="table-responsive">
                <table class="table table-striped table-responsive" style="border-left: 1px solid #f0f0f0;">
                    <tbody>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                难度：
                                <span class="label label-success round" style="float:right;">简单</span>
                            </td>
                        </tr>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                时/空限制：
                                <span style="float:right;">1s / 64MB</span>
                            </td>
                        </tr>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                总通过数：
                                <span style="float:right;">57365</span>
                            </td>
                        </tr>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                总尝试数：
                                <span style="float: right;">97354</span>
                            </td>
                        </tr>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                来源：
                                <span style="float: right;">背包九讲 , 模板题</span>
                            </td>
                        </tr>
                        <tr>
                            <td style="padding: 15px 8px 15px 8px;">
                                <span class="problem-algorithm-tag" style="cursor: pointer">算法标签<span class="caret"></span></span>
                                <div class="problem-algorithm-tag-field" style="display: none;"></div>
                                <script>
                                    $(document).ready(function () {
                                        let $tag = $('.problem-algorithm-tag');
                                        let $field = $('.problem-algorithm-tag-field');
                                        let keywords = "背包问题,DP".replace('，', ',').split(',');
                                        for (let i = 0; i < keywords.length; i ++ ) {
                                            let keyword = keywords[i].trim();
                                            if (keywords) {
                                                let $span = $(`<a href="/problem/search/1/?search_content=${keyword}"` +
                                                        `style="text-decoration: none;" target="_blank">` +
                                                    `<span class="problem-algorithm-tag-field-item">${keyword}</span></a>`);
                                                $field.append($span);
                                            }
                                        }

                                        $tag.click(function () {
                                            if ($field.is(":visible")) {
                                                $field.hide();
                                            } else {
                                                $field.show();
                                            }
                                        });
                                    });
                                </script>
                            </td>
                        </tr>
                    </tbody>
                </table>
            </div>
        </div>
    </div>
    <hr>
    

<div id="code_tool_bar">
    
        <button id="open_ac_saber_btn" class="btn btn-link"
                style="position: relative; left: 10px; top: 10px; font-size: 18px;">
            挑战模式
        </button>
        <script>
            $('#open_ac_saber_btn').click(function () {
                desktop_state.window.open_outer_window(
                    desktop_state.os.builtin.application.applications.ac_saber,
                    `menu_training_problem&chapter_name=基础知识` +
                    `&session_name=快速排序&move_right_cnt=0` +
                    `&move_down_cnt=0&problem_number=2`
                );
            });
        </script>
    
    <button class="btn btn-link pull-right" data-toggle="modal" data-target="#code_editor_confg_modal" title="编辑器设置">
        <span class="glyphicon glyphicon-cog editor_tool_btn"></span>
    </button>
    <button class="btn btn-link pull-right" data-toggle="modal" id="code-editor-refresh-btn" title="代码重置">
        <span class="glyphicon glyphicon-refresh editor_tool_refresh_btn"></span>
    </button>
    <div class="code_editor_option_language form-group" style="float: right; margin: 8px 10px 0 10px;" title="选择编程语言">
        <select name="language" style="height: 40px; width: 220px; border-radius: 4px;" class="form-control code-editor-option" id="id_language">
  <option value="1" selected>C++</option>

  <option value="2">C</option>

  <option value="3">Java</option>

  <option value="4">Python</option>

  <option value="5">Javascript</option>

  <option value="6">Python3</option>

  <option value="8">Go</option>

</select>
    </div>
    <div class="modal fade" id="code_editor_confg_modal">
        <div class="modal-dialog" style="width: 85%; max-width: 600px;">
            <div class="modal-content" style="margin-top: auto;">
                <div class="modal-header">
                    <button type="button" class="close" data-dismiss="modal" aria-hidden="true">
                        &times;
                    </button>
                    <div class="modal-title code-editor-option-head">
                        代码编辑器设置
                    </div>
                </div>
                <hr style="margin: 0 0 10px 0;">
                <div class="modal-body">
                    <div class="row">
                        <div class="col-sm-8 col-xs-12">
                            <div class="code-editor-option-title">
                                界面风格
                            </div>
                            <div class="code_editor_option_theme visible-xs-block">
                                <select name="theme_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_theme_option">
  <option value="1" selected>Textmate</option>

  <option value="2">Monoka</option>

  <option value="3">Eclipse</option>

</select>
                            </div>
                            <div class="code-editor-option-description">
                                对白色界面感到厌倦了吗？可以尝试其他的背景和代码高亮风格。
                            </div>
                        </div>
                        <div class="code_editor_option_theme col-sm-4 hidden-xs">
                            <select name="theme_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_theme_option">
  <option value="1" selected>Textmate</option>

  <option value="2">Monoka</option>

  <option value="3">Eclipse</option>

</select>
                        </div>
                    </div>
                    <hr>
                    <div class="row">
                        <div class="col-sm-8 col-xs-12">
                            <div class="code-editor-option-title">
                                编辑类型
                            </div>
                            <div class="code_editor_option_key_binding visible-xs-block">
                                <select name="key_binding_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_key_binding_option">
  <option value="1" selected>Standard</option>

  <option value="2">Vim</option>

  <option value="3">Emacs</option>

</select>
                            </div>
                            <div class="code-editor-option-description">
                                更喜欢Vim或者Emacs的输入方式吗？我们也为你提供了这些选项。
                            </div>
                        </div>
                        <div class="code_editor_option_key_binding col-sm-4 hidden-xs">
                            <select name="key_binding_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_key_binding_option">
  <option value="1" selected>Standard</option>

  <option value="2">Vim</option>

  <option value="3">Emacs</option>

</select>
                        </div>
                    </div>
                    <hr>
                    <div class="row">
                        <div class="col-sm-8 col-xs-12">
                            <div class="code-editor-option-title">
                                缩进长度
                            </div>
                            <div class="code_editor_option_tab_size visible-xs-block">
                                <select name="tab_size_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_tab_size_option">
  <option value="1">2个空格</option>

  <option value="2" selected>4个空格</option>

  <option value="3">8个空格</option>

</select>
                            </div>
                            <div class="code-editor-option-description">
                                选择代码缩进的长度。默认是4个空格。
                            </div>
                        </div>
                        <div class="code_editor_option_tab_size col-sm-4 hidden-xs">
                            <select name="tab_size_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_tab_size_option">
  <option value="1">2个空格</option>

  <option value="2" selected>4个空格</option>

  <option value="3">8个空格</option>

</select>
                        </div>
                    </div>
                    <hr>
                    <div class="row">
                        <div class="col-sm-8 col-xs-12">
                            <div class="code-editor-option-title">
                                代码补全
                            </div>
                            <div class="code_editor_option_code_complete visible-xs-block">
                                <select name="code_complete_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_tab_size_option">
                                    <option value="1">无补全</option>
                                    <option value="2" selected>单词级补全</option>
                                    <option value="3">模板级补全</option>
                                </select>
                            </div>
                            <div class="code-editor-option-description">
                                写代码疲惫了吗？让我们来帮你一把。唤醒词列表在<a href="https://www.acwing.com/file_system/file/content/whole/index/content/2145234/" target="_blank">这里</a>。
                            </div>
                        </div>
                        <div class="code_editor_option_code_complete col-sm-4 hidden-xs">
                            <select name="code_complete_option" style="max-width: 220px; border-radius: 4px; margin-bottom: 10px;" class="form-control code-editor-option" id="id_tab_size_option">
                                <option value="1">无补全</option>
                                <option value="2" selected>单词级补全</option>
                                <option value="3">模板级补全</option>
                            </select>
                        </div>
                    </div>
                </div>
                <hr style="margin: 10px 0 0 0;">
                <div class="modal-footer">
                    <button type="button" class="btn btn-primary" data-dismiss="modal"  style="float: right; border-radius: 5px;">
                        确定
                    </button>
                </div>
            </div><!-- /.modal-content -->
        </div><!-- /.modal -->
    </div>
    <div>
        <form id="code-eidtor-option-update-language-form" action="/problem/content/code_editor_preference/update/language/" method="post">
            <input type="hidden" name="csrfmiddlewaretoken" value="s4bKp3icqZRTpmGeEdi0rMxmm5PQ8U6yhXDwUwABkKba2tfjBHuAVuZFmEsGRkEu">
        </form>
        <form id="code-eidtor-option-update-theme-form" action="/problem/content/code_editor_preference/update/theme/" method="post">
            <input type="hidden" name="csrfmiddlewaretoken" value="s4bKp3icqZRTpmGeEdi0rMxmm5PQ8U6yhXDwUwABkKba2tfjBHuAVuZFmEsGRkEu">
        </form>
        <form id="code-eidtor-option-update-key-binding-form" action="/problem/content/code_editor_preference/update/key_binding/" method="post">
            <input type="hidden" name="csrfmiddlewaretoken" value="s4bKp3icqZRTpmGeEdi0rMxmm5PQ8U6yhXDwUwABkKba2tfjBHuAVuZFmEsGRkEu">
        </form>
        <form id="code-eidtor-option-update-tab-size-form" action="/problem/content/code_editor_preference/update/tab_size/" method="post">
            <input type="hidden" name="csrfmiddlewaretoken" value="s4bKp3icqZRTpmGeEdi0rMxmm5PQ8U6yhXDwUwABkKba2tfjBHuAVuZFmEsGRkEu">
        </form>
    </div>
    <script>
        let code_editor_name_config_mappings = {
            "C++": "c_cpp",
            "C": "c_cpp",
             "Java": "java",
            "Python": "python",
            "Python3": "python",
            "Javascript": "javascript",
            "Go": "golang",
            "Textmate": "textmate",
            "Monoka": "monokai",
            "Eclipse": "eclipse",
            "Standard": "null",
            "Vim": "vim",
            "Emacs": "emacs",
            "2个空格": "2",
            "4个空格": "4",
            "8个空格": "8",
        };
        let problem_code_show_mappings = {};
    </script>
</div>
<div id="code_editor"></div>

    <div>
        <button id="submit_code_btn" class="btn btn-success" style="float: right; border-radius: 20px; margin: 20px 0 0 20px;">
            <span class="glyphicon glyphicon-cloud-upload" style="top: 1px;"></span>
            &nbsp;
            提交答案
            &nbsp;
        </button>
        <button id="run_code_btn" class="btn btn-default" style="float: right; border-radius: 20px; margin: 20px 0 0 0;">
            <span class="glyphicon glyphicon-play-circle" style="top: 2px;"></span>
            &nbsp;
            调试代码
            &nbsp;
        </button>
    </div>
    <div id="submit-code-status-block" style="margin-top: 75px; display: none;">
        <hr>
        <span class="submit-code-status-label">代码提交状态：</span>
        <span id="submit-code-status-value-id" class="submit-code-status-value"></span>
        &nbsp;&nbsp;
        <img id="submit-code-status-loading-gif-id" src="https://cdn.acwing.com/static/web/gif/code_status_loading.gif" width="18px;" style="margin-top: -5px;">
        <pre id="submit-code-status-compilation-log-id" class="submit-code-status-compilation-log"
             style="margin-top: 10px; border-radius: 5px; padding: 10px; background-color: #f2dede; border-color: #ebccd1; color: #a94442;">
        </pre>
    </div>
    <div id="run-code-status-block" class="panel panel-default" style="margin-top: 75px;">
        <div class="panel-heading">
            <span class="submit-code-status-label">代码运行状态：</span>
            <span id="run-code-status-value-id" class="submit-code-status-value"></span>
            &nbsp;&nbsp;
            <img id="run-code-status-loading-gif-id" src="https://cdn.acwing.com/static/web/gif/code_status_loading.gif" width="18px;" style="margin-top: -5px;">
            <button type="button" id="run-code-status-block-remove-btn" class="close">
                &times;
            </button>
        </div>
        <div class="panel-body" style="padding: 25px;">
            <label for="run-code-stdin" style="font-weight: normal; font-size: 15px;">输入</label>
            <textarea id="run-code-stdin" class="form-control autofit" maxlength="2000"
                      rows="1"
                      style="background-color: #f8f8f8; border-radius: 5px; resize: none; font-family: monospace; overflow: hidden; min-height: 40px;"
            >4 5
1 2
2 4
3 4
4 5</textarea>
            <br>
            <span style="font-weight: normal; font-size: 15px;">输出</span>
            <pre id="run-code-stdout" style="background-color: #f8f8f8; border-radius: 5px; margin-top: 5px; min-height: 40px;"></pre>
            <div id="run-code-expected-stdout-block" style="margin-top: 20px; display: none;">
                <span style="font-weight: normal; font-size: 15px;">标准答案</span>
                <pre id="run-code-expected-stdout" style="background-color: #f8f8f8; border-radius: 5px; margin-top: 5px; min-height: 40px;"></pre>
            </div>
            <span id="run-code-time" style="display: none;"></span>
        </div>
    </div>


        </div>
    </div>
</div>
</div>
    <footer id="acwing_footer" class="footer">
    <div class="container">
        <hr>
        <div class="row">
            <div class="col-sm-8 copyright">
                <span>
                    © 2018-2021 AcWing 版权所有
                    &nbsp;|&nbsp;
                    <a href="http://beian.miit.gov.cn/">京ICP备17053197号-1</a>
                </span>
            </div>
            <div class="text-right col-sm-4 region-us">
                <div class="links">
                    <a href="/footer/contactus/">联系我们</a>
                    &nbsp;|&nbsp;
                    <a href="/footer/faq/">常见问题</a>
                    &nbsp;|&nbsp;
                    <a target="cyxyv" href="https://v.yunaq.com/certificate?domain=www.acwing.com&from=label&code=90030" style="display: none;">
                        <img height="30px" src="https://aqyzmedia.yunaq.com/labels/label_sm_90030.png" alt="行业认证">
                    </a>
                </div>
            </div>
        </div>
    </div>
</footer>
</div>







<div id="modal-warning" class="modal modal-message modal-warning fade" style="display: none;" aria-hidden="true">
    <div class="modal-dialog">
        <div class="modal-content">
            <div class="modal-header">
                <i class="glyphicon glyphicon-warning-sign"></i>
            </div>
            <div id="warning_message_content" class="modal-body"></div>
            <div class="modal-footer">
                <button type="button" class="btn btn-warning" data-dismiss="modal">OK</button>
            </div>
        </div> <!-- / .modal-content -->
    </div> <!-- / .modal-dialog -->
</div>


    <script>
        let GLOBAL_PROBLEM_MODE = "normal";
        let GLOBAL_PROBLEM_ACTIVITY_ID = 0;
        let GLOBAL_PROBLEM_RECORD = [];
        let GLOBAL_PROBLEM_CHALLENGE_MODE_STATUS = 0;   // 0 表示未结束，1表示赢，2表示输
        
    </script>
    
    
    <script src="https://cdn.acwing.com/static/web/js/editor/code_editor-0.0.7.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/editor/debug_code-0.0.22.js"></script>
    <script>
        let PROBLEM_ID = 2;
    </script>





<script src="https://cdn.acwing.com/static/web/js/copy_with_link.js"></script>
<script>
    let article_author = "";
    if (article_author.length === 0) article_author = "AcWing";
    let VIDEO_CONTENT_WATERMARK_LOGO_URL = "https://cdn.acwing.com/static/web/img/32X32.ico";
</script>
<script src="https://cdn.acwing.com/static/plugins/js/highlight.min.js"></script>
<script type="text/x-mathjax-config">
        MathJax.Hub.Config({
          tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
          showMathMenu: false,
        });
</script>
<script type="text/javascript" src="https://cdn.acwing.com/static/MathJax-2.6-latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
    $('pre').each(function(i, block){
        hljs.highlightBlock(block);
    });
</script>

    <script src="https://cdn.acwing.com/static/web/js/file_system/file/operation/collect/favorite.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/file_system/file/operation/vote/vote.js"></script>
    <script type="text/javascript" src="https://cdn.acwing.com/static/web/js/file_system/file/operation/content/delete-0.0.4.js"></script>
    <script type="text/javascript" src="https://cdn.acwing.com/static/web/js/file_system/file/operation/comment/add-0.0.4.js"></script>
    <script type="text/javascript" src="https://cdn.acwing.com/static/web/js/file_system/file/operation/comment/delete-0.0.4.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/file_system/file/content/abstract/vote-0.0.1.js"></script>
    <script src="https://cdn.acwing.com/static/web/js/file_system/file/content/abstract/collect-0.0.2.js"></script>

<script>
    
    
    window.onbeforeunload = function (ev) {

        
            let windows = desktop_state.window.windows;
            for (let i = 0; i < windows.length; i ++ ) {  // 把所有未关闭的窗口关闭
                if (windows[i]) {
                    desktop_state.window.close(i);
                }
            }
        

        let notify = false;
        for (let i = 0; i < onbeforeunload_functions.length; i ++ ){
            let ret = onbeforeunload_functions[i]();
            if (ret){
                notify = true;
            }
        }
        if (notify){
            return true;
        }
    };

    let CLICK_URL_STATUS = "status";
    let CLICK_URL_COUNT = "count";
    let CLICK_URL_CLICK = "click";
    let CLICK_URL = "/" + CLICK_URL_STATUS + "/" + CLICK_URL_COUNT + "/" + CLICK_URL_CLICK + "/";
</script>
<script src="https://cdn.acwing.com/static/web/js/status/click.js"></script>
</body>
</html>